package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         1071,
		Discription: "两个字符串的最大公因子字符串(s3=gcd(s1,s2), s1=s3+s3+...,s2=s3+s3...)",
		Level:       2,
		Labels: map[string]int{
			"数学":   1,
		},
	})
}

//最大公因子字符串的长度必然是两个字符串长度的公因子
//从最大公因数开始往下遍历，碰到满足条件的直接返回
func GcdOfStrings(str1 string, str2 string) string {
	m := len(str1)
	n := len(str2)
	for step := gcd(m, n); step >= 1; step-- {
		//字符串长度无法整除步长、起始步长范围内两个字符串不相等
		if m%step != 0 || n%step != 0 || str1[:step] != str2[:step] {
			continue
		}

		match := true
		//依次检查两个字符串是否能由该字符串构成
		for i := step; i+step <= m; i += step {
			if str1[i-step:i] != str1[i:i+step] {
				match = false
				break
			}
		}

		if !match {
			continue
		}

		for i := step; i+step <= n; i += step {
			if str2[i-step:i] != str2[i:i+step] {
				match = false
				break
			}
		}

		if !match {
			continue
		}

		return str1[:step]
	}

	return ""
}

func gcd(a, b int) int {
	for b != 0 {
		mod := a % b
		a = b
		b = mod
	}

	return a
}